from typing import List

INF = 10 ** 9

DEPART = 0
ARRIVE = 1
DONE = 2
OPEN = 3
CLOSE = 4
MORNING_RUSH_HOUR_START = 5
MORNING_RUSH_HOUR_STOP = 6
AFTERNOON_RUSH_HOUR_START = 7
AFTERNOON_RUSH_HOUR_STOP = 8
DEADLINE = 9

PRINT = lambda *args: 0


def goto(h1, m1, h2, m2, jiancedian):
    """
    事件驱动模拟
    """
    id_, distance, wait = jiancedian
    t_depart = h1 * 60 + m1
    t_deadline = h2 * 60 + m2
    t_arrive = t_depart + distance * 10
    t_open = 8*60
    t_close = 20*60
    events = [
        (t_depart, DEPART),
        (t_deadline, DEADLINE),
        (t_arrive, ARRIVE),
        (t_open, OPEN),
        (t_close, CLOSE),
        (8*60, MORNING_RUSH_HOUR_START),
        (10*60, MORNING_RUSH_HOUR_STOP),
        (12*60, AFTERNOON_RUSH_HOUR_START),
        (14*60, AFTERNOON_RUSH_HOUR_STOP)
    ]
    events.sort()
    add_per_min = 0
    subtract_per_min = 0
    queue_num = 0
    prev_t = None
    for t, e in events:
        if e == DEPART:
            queue_num = wait
            prev_t = t
            PRINT(t, e, queue_num)
        elif e == DEADLINE or e == CLOSE:
            PRINT(t, e, queue_num)
            return None
        elif e == ARRIVE:
            if prev_t is not None:
                queue_num = max(0, queue_num + (add_per_min - subtract_per_min) * (t - prev_t))
            t_done = max(t_open, t) + queue_num
            if t_done > min(t_deadline, t_close):
                return None
            else:
                return id_, t_done, t_arrive
        elif e == OPEN:
            if prev_t is not None:
                queue_num = max(0, queue_num + (add_per_min - subtract_per_min) * (t - prev_t))
            subtract_per_min = 1
            prev_t = t
            PRINT(t, e, queue_num)
        elif e == MORNING_RUSH_HOUR_START:
            if prev_t is not None:
                queue_num = max(0, queue_num + (add_per_min - subtract_per_min) * (t - prev_t))
            add_per_min = 3
            prev_t = t
            PRINT(t, e, queue_num)
        elif e == MORNING_RUSH_HOUR_STOP:
            if prev_t is not None:
                queue_num = max(0, queue_num + (add_per_min - subtract_per_min) * (t - prev_t))
            add_per_min = 0
            prev_t = t
            PRINT(t, e, queue_num)
        elif e == AFTERNOON_RUSH_HOUR_START:
            if prev_t is not None:
                queue_num = max(0, queue_num + (add_per_min - subtract_per_min) * (t - prev_t))
            add_per_min = 10
            prev_t = t
            PRINT(t, e, queue_num)
        elif e == AFTERNOON_RUSH_HOUR_STOP:
            if prev_t is not None:
                queue_num = max(0, queue_num + (add_per_min - subtract_per_min) * (t - prev_t))
            add_per_min = 0
            prev_t = t
            PRINT(t, e, queue_num)

def hesuan1(h1, m1, h2, m2, jiancedian_list: List[List[int]]):
    t_depart = 60 * h1 + m1
    lst = [goto(h1, m1, h2, m2, jiancedian) for jiancedian in jiancedian_list]
    lst = [x for x in lst if x]
    lst.sort(key=lambda x: (x[1], x[2], x[0]))
    lst = [(x[0], x[1] - t_depart, x[2] - t_depart) for x in lst]
    return lst

def goto2(h1, m1, h2, m2, jiancedian):
    """
    暴力模拟
    """
    id_, distance, wait = jiancedian
    t_depart = h1 * 60 + m1
    t_deadline = h2 * 60 + m2
    t_arrive = t_depart + distance * 10
    t_open = 8 * 60
    t_close = 20 * 60
    t_mrh0 = 8 * 60
    t_mrh1 = 10 * 60
    t_arh0 = 12 * 60
    t_arh1 = 14 * 60
    queue_num = wait

    for t in range(t_depart, min(t_deadline, t_close)+1):
        if t == t_arrive:
            t_done = max(8*60, t) + queue_num
            if t_done > min(t_deadline, t_close):
                return None
            return id_, t_done, t_arrive
        if t_mrh0 <= t < t_mrh1:
            queue_num += 3
        if t_arh0 <= t < t_arh1:
            queue_num += 10
        if t_open <= t < t_close:
            queue_num -= 1
            queue_num = max(0, queue_num)
        if t == min(t_deadline, t_close):
            return None
    return None

def hesuan2(h1, m1, h2, m2, jiancedian_list: List[List[int]]):
    t_depart = 60 * h1 + m1
    lst = [goto2(h1, m1, h2, m2, jiancedian) for jiancedian in jiancedian_list]
    lst = [x for x in lst if x]
    lst.sort(key=lambda x: (x[1], x[2], x[0]))
    lst = [(x[0], x[1] - t_depart, x[2] - t_depart) for x in lst]
    return lst


def test():
    cases = [
        (10, 30, 14, 50, [[1, 10, 10], [2, 8, 20], [3, 21, 3]]),
        (17, 10, 22, 10, [[5, 17, 80]]),
        (14, 33, 17, 23, [[2, 17, 96]]),
        (0, 9, 13, 58, [[0, 50, 61], [1, 0, 17], [2, 43, 1]])
    ]
    for args in cases:
        res1 = hesuan1(*args)
        res2 = hesuan1(*args)
        if res1 != res2:
            print(args, res1, res2)
test()


def random_test():
    for _ in range(10000):
        import random
        h1 = random.randint(0, 23)
        h2 = random.randint(0, 23)
        m1 = random.randint(0, 59)
        m2 = random.randint(0, 59)

        n = random.randint(1, 10)
        jiancedian_list = []
        for i in range(n):
            id_ = i
            distance = random.randint(0, 150)
            queue_num = random.randint(0, 1000)
            jiancedian_list.append([id_, distance, queue_num])

        res1 = hesuan1(h1, m1, h2, m2, jiancedian_list)
        res2 = hesuan2(h1, m1, h2, m2, jiancedian_list)
        if res1 != res2:
            print((h1, m1, h2, m2, jiancedian_list), res1, res2)
            assert 0
random_test()

